package com.clstu.leetcode;

import java.util.Stack;

/**
 * 只用递归函数实现栈的逆序
 */
public class StackReverse {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(3);
        stack.push(2);
        stack.push(1);
        System.out.println(stack);
//        System.out.println(getButton(stack));
//        System.out.println(stack);
        //不用额外的结构,只是用递归实现栈的逆序
        reverse(stack);
        System.out.println(stack);
    }

    //编写方法返回弹出栈的底部
    public static Integer getButton(Stack<Integer> stack){
        int result = stack.pop();
        //判断是否栈空,如果栈空,说明是最底下的元素直接返回
        if(stack.isEmpty()){
            return  result;
        }
        //如果栈不空,不是最后一个元素,向下要,再把弹出的压回去
        int last = getButton(stack);
        stack.push(result);
        return last;
    }

    //编写方法递归实现栈的逆序
    public static void reverse(Stack<Integer> stack){
        //先判断是否栈空,如果栈空直接返回
        if(stack.isEmpty()) return;
        //一层一层的弹出栈底,再一层一层的压回去就可以实现逆序了.
        Integer button = getButton(stack);
        reverse(stack);
        stack.push(button);
    }
}
